#include <bits/stdc++.h>

#define in read()
#define fi first
#define se second
#define pb push_back
#define y1 y_alpha_1

using namespace std;

using ll = long long;
using db = double;
using vec = vector<int>;
using pii = pair<int,int>;

int read() {
	int x = 0; bool f = 0; char ch = getchar();
	while(!isdigit(ch)) f |= ch == '-',ch = getchar();
	while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48),ch = getchar();
	return f ? -x : x;
}

const int N = 2e4 + 10;
const int MK = 5e5 + 10;
const int BSIZ = 2.5e7 + 10;

int n,K,a[N],v[N],fa[N];
int f[BSIZ],g[BSIZ],ans,s[N];
vec G[N];

inline int pos(int x,int k) { return (x - 1) * (K + 1) + k;}

void calc(int *f,int a,int v) {
	if(a == 0) return; static int q[N],p[N]; int ql = 1, qr = 0;
	for(int i = 0;i <= K;i++) {
		f[i] -= i * v;
		while(ql <= qr && f[i] >= f[q[qr]]) qr--;
		q[++qr] = i;
		while(ql <= qr && i - q[ql] > a) ql++;
		p[i] = f[q[ql]] + i * v;
	}
	for(int i = 0;i <= K;i++) f[i] = p[i];
}

void dfsL(int x) {
	calc(&f[pos(x,0)],a[x] - 1,v[x]);
	for(auto y : G[x]) {
		for(int j = 0;j <= K;j++) f[pos(y,j)] = f[pos(x,j)];
		dfsL(y); for(int j = 1;j <= K;j++) f[pos(x,j)] = max(f[pos(x,j)],f[pos(y,j - 1)] + v[y]);
	}
}

void dfsR(int x,int s) {
	s += v[x];
	for(auto y : G[x]) {
		for(int j = 0;j <= K;j++) g[pos(y,j)] = g[pos(x,j)];
		dfsR(y,s); for(int j = 1;j <= K;j++) g[pos(x,j)] = max(g[pos(x,j)],g[pos(y,j - 1)] + v[y]);
	}
	if(!G[x].size()) for(int j = 0;j <= K;j++) ans = max(ans,f[pos(x,j)] + g[pos(x,K - j)] + s);
	calc(&g[pos(x,0)],a[x] - 1,v[x]);
}

void solve() {
	for(int i = 1;i <= n;i++) { vec t; G[i].swap(t); }
	n = in,K = in; for(int i = 1;i <= n;i++) fa[i] = in,a[i] = in,v[i] = in,G[fa[i]].pb(i);
	for(int i = pos(1,0);i <= pos(1,K);i++) f[i] = g[i] = 0;
	ans = 0; dfsL(1); for(int i = 1;i <= n;i++) reverse(G[i].begin(),G[i].end()); dfsR(1,0);
	printf("%d\n",ans);
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	for(int t = in;t;t--) solve();
	return 0;
}
